#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MEMORYLENGTH 4

void printArr(int *arr, int length)
{
    for (size_t i = 0; i < length; i++)
    {
        /* code */
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void printMat(int arr[MEMORYLENGTH][MEMORYLENGTH])
{
    for (size_t i = 0; i < MEMORYLENGTH; i++)
    {
        /* code */
        for (int j = 0; j < MEMORYLENGTH; ++j)
        {
            printf("%d ", arr[i][j]);
        }
        puts("");
    }
    printf("\n");
}

void queuePush(int item, int *count, int *arr, int arrLength)
{

    for (size_t i = 0; i < *count; i++)
    {
        if (arr[i] == item)
        {
            return;
        }
    }

    if (arrLength <= 0)
    {
        printf("somethong wrong!\n");
        return;
    }

    if (*count != arrLength)
    {
        for (int i = arrLength - 1; i >= 1; --i)
        {
            arr[i] = arr[i - 1];
        }
        arr[0] = item;
        (*count)++;
    }
    else
    {

        if (arrLength == 1)
        {
            arr[0] = item;
            return;
        }

        for (int i = arrLength - 1; i >= 1; --i)
        {
            arr[i] = arr[i - 1];
        }
        arr[0] = item;
    }
}
void stackPush(int item, int *count, int *arr, int arrLength)
{

    for (size_t i = 0; i < *count; i++)
    {
        if (arr[i] == item)
        {
            if (i == (*count) - 1)
                return;
            else
            {

                for (int j = i; j < (*count) - 1; ++j)
                {
                    arr[j] = arr[j + 1];
                }
                arr[(*count) - 1] = item;
            }
        }
    }

    if (arrLength <= 0)
    {
        printf("somethong wrong!\n");
        return;
    }
    if (*count == arrLength)
    {
        arr[0] = item;
    }
    else
    {
        arr[*count] = item;
        (*count)++;
    }
}

void FIFO(int *input, int inputLength, int *output, int outputLength)
{

    printf("FIFO test:\n");
    int count = 0;
    for (int i = 0; i < inputLength; ++i)
    {
        queuePush(input[i], &count, output, outputLength);
        printArr(output, outputLength);
    }
}
void queuePushSecondChance(int item, int *count, int *arr, int arrLength, int *markedArr)
{

    for (size_t i = 0; i < *count; i++)
    {
        if (arr[i] == item)
        {
            if (markedArr[i] == 1)
            {
                for(int j = i ; j >= 1 ; --j){
                    arr[j] = arr[j-1];
                    markedArr[j] = markedArr[j-1];
                }
                arr[0] = item;
                markedArr[0] = 0;
            } else{
                markedArr[i] = 1;
            }
            return;
        }
    }

    if (arrLength <= 0)
    {
        printf("somethong wrong!\n");
        return;
    }

    if (*count != arrLength)
    {
        for (int i = arrLength - 1; i >= 1; --i)
        {
            arr[i] = arr[i - 1];
            markedArr[i] = markedArr[i - 1];
        }
        arr[0] = item;
        (*count)++;
    }
    else
    {

        if (arrLength == 1)
        {
            arr[0] = item;
            return;
        }

        for (int i = arrLength - 1; i >= 1; --i)
        {
            arr[i] = arr[i - 1];
            markedArr[i] = markedArr[i-1];
        }
        arr[0] = item;
    }
}
void SecondChance(int *input, int inputLength, int *output, int outputLength)
{

    printf("SecondChance test:\n");
    int count = 0;
    int markedArr[MEMORYLENGTH];
    memset(markedArr, 0, 4 * MEMORYLENGTH);
    for (int i = 0; i < inputLength; ++i)
    {
        queuePushSecondChance(input[i], &count, output, outputLength, markedArr);
        printArr(output, outputLength);
        printf("Mark Arr: ");
        printArr(markedArr, MEMORYLENGTH);
    }
}

void LRUwithStack(int *input, int inputLength, int *output, int outputLength)
{

    printf("LRUwithStack test:\n");
    int count = 0;
    for (int i = 0; i < inputLength; ++i)
    {
        stackPush(input[i], &count, output, outputLength);
        printArr(output, outputLength);
    }
}

void matrixPush(int item, int *count, int *arr, int arrLength, int mat[MEMORYLENGTH][MEMORYLENGTH])
{

    for (size_t i = 0; i < *count; i++)
    {
        if (arr[i] == item)
        {
            for (int j = 0; j < MEMORYLENGTH; ++j)
            {
                mat[i][j] = 1;
            }
            for (int j = 0; j < MEMORYLENGTH; ++j)
            {
                mat[j][i] = 0;
            }
            return;
        }
    }

    if (arrLength <= 0)
    {
        printf("somethong wrong!\n");
        return;
    }
    if (*count == arrLength)
    {

        int sum = RAND_MAX;
        int sumIndex = 0;
        for (size_t i = 0; i < MEMORYLENGTH; i++)
        {
            int tempsum = 0;
            for (size_t j = 0; j < MEMORYLENGTH; j++)
            {
                /* code */
                tempsum += mat[i][j];
            }

            if (tempsum < sum)
            {
                sum = tempsum;
                sumIndex = i;
            }
        }

        arr[sumIndex] = item;

        for (int j = 0; j < MEMORYLENGTH; ++j)
        {
            mat[sumIndex][j] = 1;
        }
        for (int j = 0; j < MEMORYLENGTH; ++j)
        {
            mat[j][sumIndex] = 0;
        }
    }
    else
    {
        arr[*count] = item;
        for (int j = 0; j < MEMORYLENGTH; ++j)
        {
            mat[*count][j] = 1;
        }
        for (int j = 0; j < MEMORYLENGTH; ++j)
        {
            mat[j][*count] = 0;
        }
        (*count)++;
    }
}

void LRUwithMatrix(int *input, int inputLength, int *output, int outputLength)
{

    printf("LRUwithMatrix test:\n");
    int mat[MEMORYLENGTH][MEMORYLENGTH];
    memset(mat, 0, 4 * MEMORYLENGTH * MEMORYLENGTH);
    int count = 0;
    for (int i = 0; i < inputLength; ++i)
    {
        matrixPush(input[i], &count, output, outputLength, mat);
        printArr(output, outputLength);
        printMat(mat);
    }
}

int main(int argc, char const *argv[])
{
    int input[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};

    int memory[MEMORYLENGTH];

    printf("input: ");
    printArr(input, 20);
    //LRUwithStack(input, 20, memory, MEMORYLENGTH);
    //LRUwithMatrix(input, 20, memory, MEMORYLENGTH);
    //FIFO(input, 20, memory, MEMORYLENGTH);
    SecondChance(input, 20, memory, MEMORYLENGTH);
    
    return 0;
}
